# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

from BinaryTree import *

class Solution:
	# @param {ListNode} head
	# @return {TreeNode}
	def sortedListToBST(self, head):
		size = 0
		h = head
		size = 0
		while h:
			size += 1
			h = h.next

		return self.__btree(head, 0, size-1)

	def __btree(self, head, left, right):
		if left > right:
			return None
		mid_node = (right + left) / 2
		left_child = self.__btree(head, left, mid_node-1)
		root = TreeNode(head.val)
		root.left = left_child
		if head.next:
			head.val = head.next.val
			head.next = head.next.next
		root.right = self.__btree(head, mid_node+1, right)
		return root

if __name__ == '__main__':
	h = t = ListNode(None)
	for i in [1,3,4,5,6,7]:
		t.next = ListNode(i)
		t = t.next

	root = Solution().sortedListToBST(h.next)
	tree = BinaryTree(root)
	tree.display()